package special;

import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

public class LeeCode_LCP_74 {
    public static void main(String[] args) {
        System.out.println(fieldOfGreatestBlessing(new int[][]{{1, 1, 100}}));
        System.out.println(fieldOfGreatestBlessing(new int[][]{{0,0,1},{1,0,1}}));
    }

    private static int fieldOfGreatestBlessing(int[][] forceField) {
        TreeSet<Long> xTree = new TreeSet<>();
        TreeSet<Long> yTree = new TreeSet<>();
        for (int[] f : forceField) {
            xTree.add(f[0] * 2L + f[2]);
            xTree.add(f[0] * 2L - f[2]);
            yTree.add(f[1] * 2L - f[2]);
            yTree.add(f[1] * 2L + f[2]);
        }
        List<Long> xList = new ArrayList<>(xTree);
        List<Long> yList = new ArrayList<>(yTree);
        int xLen = xList.size() + 2;
        int yLen = yList.size() + 2;
        int[][] d = new int[xLen][yLen];
        for (int[] f : forceField) {
            int x1 = binarySearch(xList, f[0] * 2L - f[2]);
            int x2 = binarySearch(xList, f[0] * 2L + f[2]);
            int y1 = binarySearch(yList, f[1] * 2L - f[2]);
            int y2 = binarySearch(yList, f[1] * 2L + f[2]);
            change(d, x1, y1, x2, y2);
        }
        int ans = 0;
        for (int i = 1; i < xLen; i++) {
            for (int j = 1; j < yLen; j++) {
                d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];
                ans = Math.max(ans, d[i][j]);
            }
        }
        return ans;
    }
    private static void change(int[][] d, int x1, int y1, int x2, int y2){
        d[x1 + 1][y1 + 1] += 1;
        d[x2 + 2][y1 + 1] -= 1;
        d[x1 + 1][y2 + 2] -= 1;
        d[x2 + 2][y2 + 2] += 1;
    }
    private static int binarySearch(List<Long> list, long goal){
        int len = list.size();
        int l = 0, r = len - 1;
        while (l < r){
            int m = (l + r) >>> 1;
            if (list.get(m) < goal){
                l = m + 1;
            }else if (list.get(m) > goal){
                r = m - 1;
            }else {
                r = m;
            }
        }
        return l;
    }
}
